Décomposition en facteurs premiers et PGCD

Propriété

Soit $m$ et $n$ deux entiers supérieurs ou égaux à $2$ . On suppose, quitte à utiliser des exposants nuls, que $m$ et $n$ se décomposent en produits de facteurs premiers sous la forme :

$n=p_1^{{\alpha }_1}{p}_2^{{\alpha }_2}...p_k^{{\alpha }_k}$    et    $m=p_1^{{\beta }_1}{p}_2^{{\beta }_2}...p_k^{{\beta }_k}$ .

On a alors :  $\mathrm{PGCD}(n;m)=p_1^{min({\alpha }_1;{\beta }_1)}{p}_2^{min({\alpha }_2;{\beta }_2)}...p_k^{min({\alpha }_k;{\beta }_k)}$ .

Démonstration

Soit $d$ un diviseur commun à $n$ et $m$ . Alors 
$d=p_1^{{\gamma }_1}{p}_2^{{\gamma }_2}...p_k^{{\gamma }_k}$  avec, pour tout $i\in \{1;...;k\}$ , $\{\begin{array}{l}0⩽{\gamma }_i⩽{\alpha }_i\\ 0⩽{\gamma }_i⩽{\beta }_i\end{array}$  
autrement dit $0⩽{\gamma }_i⩽min({\alpha }_i;{\beta }_i)$ .

La plus grande valeur possible pour $d$ , qui est le PGCD de $n$ et $m$ , est donc bien 
$\mathrm{PGCD}(n;m)=p_1^{min({\alpha }_1;{\beta }_1)}{p}_2^{min({\alpha }_2;{\beta }_2)}...p_k^{min({\alpha }_k;{\beta }_k)}$ .